# 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
# candidates 中的数字可以无限制重复被选取。


class Solution:
    def combinationSum(self, candidates, target):
        self.res_list = []
        self.find_solution(target, [], candidates)
        return self.res_list

    def find_solution(self, target, tar_list, candidates):
        for index, num in enumerate(candidates):
            mid_num = target - num
            if mid_num == 0:
                mid_tar_list = tar_list[:]
                mid_tar_list.append(num)
                mid_tar_list.sort()
                if mid_tar_list not in self.res_list:
                    self.res_list.append(mid_tar_list)
                continue
            elif mid_num < 0:
                continue
            else:
                mid_tar_list = tar_list[:]
                mid_tar_list.append(num)
                self.find_solution(mid_num, mid_tar_list, candidates[index:])


a = Solution()
print(a.combinationSum([8, 7, 4, 3], 11))
